package gold.digger;

import gold.utils.InputUtil;
import org.fusesource.leveldbjni.All;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC432 {
    public long startExecuteTime = System.currentTimeMillis();


    class AllOne {
        //记录 key -> 个数
        Map<String, Integer> keyMap;
        //记录 个数 -> key1-key2-key3-key   --->使用了TreeMap查询时候就是O(log k) k 在[1, n]之间
        TreeMap<Integer, LinkedList<String>> countMap;
        //记录 key -> 在链表中的索引
        Map<String, Integer> keyIndexMap;

        public AllOne() {
            keyMap = new HashMap<>();
            countMap = new TreeMap<>();
            keyIndexMap = new HashMap<>();
        }

        public void inc(String key) {
            int oldCount = keyMap.getOrDefault(key, 0);
            if (oldCount > 0) {
                //之前就存在, 则移除旧的
                remove(key, oldCount);
            }
            //新增新的
            insert(key, oldCount + 1);
        }

        private void insert(String key, int count) {
            //更新keyMap中该key个数
            keyMap.put(key, count);
            //countMap中写入 个数 - key关系
            LinkedList<String> list = countMap.getOrDefault(count, new LinkedList<>());
            list.add(key);
            countMap.put(count, list);
            //记录key 在 链表的位置
            keyIndexMap.put(key, list.size() - 1);
        }

        private void remove(String key, int count) {
            keyMap.remove(key);
            //移除countMap中的key, 需要先找到该key的索引, 将list尾的替换key所在索引位置, 再删除最后元素
            int index = keyIndexMap.get(key);
            LinkedList<String> list = countMap.get(count);
            //若只有一个, 则删除即可
            if (list.size() == 1) {
                countMap.remove(count);
                return;
            }
            //O(1)重点 (好像有个术语叫什么动态数组), 使用末尾元素代替当前元素, 记得更新末尾元素在keyIndexMap的位置, 最后删除末尾元素
            String lastKey = list.getLast();
            list.set(index, lastKey);
            keyIndexMap.put(lastKey, index);
            list.removeLast();
        }

        public void dec(String key) {
            int oldCount = keyMap.getOrDefault(key, 0);
            //删除旧的
            remove(key, oldCount);
            if (oldCount > 1) {
                //之前有多个, 则需要新增个数-1的记录
                insert(key, oldCount - 1);
            }
        }

        public String getMaxKey() {
            Map.Entry<Integer, LinkedList<String>> entry = countMap.lastEntry();
            if (entry == null || entry.getValue() == null || entry.getValue().isEmpty()) {
                return "";
            }
            //取个数最少的链表中第一个元素(取头尾都是O(1))
            return entry.getValue().getFirst();
        }

        public String getMinKey() {
            Map.Entry<Integer, LinkedList<String>> entry = countMap.firstEntry();
            if (entry == null || entry.getValue() == null || entry.getValue().isEmpty()) {
                return "";
            }
            //取个数最多的链表中第一个元素(取头尾都是O(1))
            return entry.getValue().getFirst();
        }
    }


    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new AllOne().toString());
    }

    public static void main(String[] args) throws Exception {
        LC432 an = new LC432();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
